//https://leetcode.cn/problems/minimize-malware-spread-ii/?envType=daily-question&envId=2024-04-17https://leetcode.cn/problems/minimize-malware-spread-ii/?envType=daily-question&envId=2024-04-17

class Solution {
public:
    class UnionFind {
    public:
        vector<int> fa;
        int cnt;
        UnionFind(int n)
        {
            fa.resize(n);
            cnt=n;
            for(int i=0;i<n;i++){
                fa[i]=i;
            }
        }

        int find(int x){
            if(fa[x]!=x){
                fa[x]=find(fa[x]);
            }
            return fa[x];
        }

        void merge(int x,int y){
            int fx=find(x);
            int fy=find(y);
            if(fx!=fy){
                fa[fx]=fy;
            }
        }
    };

    int minMalwareSpread(vector<vector<int>>& graph, vector<int>& initial) {
        int n=graph.size();
        int effectednum=n,index=0;
        for(int del:initial){
            UnionFind uf(n);
            for(int i=0;i<n;i++){
                if(i==del)  continue;
                for(int j=i+1;j<n;j++){
                    if(j==del)  continue;
                    if(graph[i][j])
                        uf.merge(i,j);
                }
            }
            int counteffect=0;
            for(int i=0;i<n;i++){
                if(i==del)  continue;
                for(int num:initial){
                    if(num==del)    continue;
                    if(uf.find(i)==uf.find(num)){
                        counteffect++;
                        break;
                    }
                }
            }
            cout<<counteffect<<endl;
            if(counteffect<effectednum){
                effectednum=counteffect;
                index=del;
            }else if(counteffect==effectednum){
                index=min(index,del);
            }
        }
        return index;
    }
};